#pragma once

namespace ssy
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node* _next;
		list_node* _prev;

		list_node(T data = T())
			: _data(data)
			, _next(nullptr)
			, _prev(nullptr)
		{

		}
	};

	template<class T, class Ref, class Ptr>
	struct list_iterator
	{
	
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> Self;

		list_iterator(Node* node)
			: _node(node)
		{

		}

		Ref operator* ()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator != (const Self& it) const
		{
			return _node != it._node;
		}

		bool operator == (const Self& it) const
		{
			return _node == it._node;
		}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

	
		Node* _node;
	};

	template<class T>
	class List
	{
	public:
		typedef list_node<T> Node;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			return _head->_next; //隐式类型转换
			//return iterator(root->next); //匿名对象
		}
		iterator end()
		{
			return _head;
		}

		const_iterator begin() const 
		{
			return _head->_next; //隐式类型转换
			//return iterator(root->next); //匿名对象
		}
		const_iterator end() const
		{
			return _head;
		}

		List()
		{
			_head = new Node();
			_head->_prev = _head;
			_head->_next = _head;
		}

		//List(const List<T>& lt)
		//	: _head(new Node())
		//{
		//	
		//	_head->_prev = _head;
		//	_head->_next = _head;

		//	Node* cur1 = lt._head->_next;
		//	Node* cur2 = _head;
		//	
		//	while (cur1 != lt. _head)
		//	{
		//		Node* newnode = new Node(cur1->_data);
		//		cur2->_next = newnode;
		//		newnode->_prev = cur2;
		//		cur1 = cur1->_next;
		//		cur2 = cur2->_next;
		//	}

		//	cur2->_next = _head;
		//	_head->_prev = cur2;
		//}

		List(const List<T>& x)
		{
			_head = new Node();
			_head->_prev = _head;
			_head->_next = _head;

			for (const auto& ch : x)
			{
				push_back(ch);
			}
		}

		//现代写法
		void swap(List<T>& x)
		{
			std::swap(_head, x._head);
		}

		List<T>& operator=(List<T> x)
		{
			swap(x);

			return *this;
		}

		//~List()
		//{
		//	Node * cur = _head->_next;
		//	while (cur != _head)
		//	{
		//		Node* next = cur->_next;
		//		delete cur;
		//		cur = next;
		//	}
		//	delete _head;
		//	_head = nullptr;
		//}

		~List()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void push_back(T data)
		{
			Node* newnode = new Node(data);
			Node* tail = _head->_prev;
			newnode->_next = _head;
			newnode->_prev = tail;
			tail->_next = newnode;
			_head->_prev = newnode;
		}

		void push_front(T data)
		{
			Node* newnode = new Node(data);
			newnode->_next = _head->_next;
			newnode->_prev = _head;
			_head->_next->_prev = newnode;
			_head->_next = newnode;
		}

		void pop_front()
        {
            Node* cur = _head->_next;

            _head->_next = cur->_next;
            cur->_next->_prev = _head;

            delete cur;
        }

        void pop_back()
        {
            Node* cur = _head->_prev;
            Node* newtail = cur->_prev;

            newtail->_next = _head;
            _head->_prev = newtail;

            delete cur;
        }



		void print()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				std::cout << cur->_data << "->";
				cur = cur->_next;
			}
			std::cout << std::endl;
		}

		//pos之前插入一个
		iterator insert(iterator pos, T data)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(data);

			newnode->_next = cur;
			newnode->_prev = cur->_prev;
			cur->_prev->_next = newnode;
			cur->_prev = newnode;

			return newnode;
		}

		//
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return next;
		}

		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

	private:
		Node* _head;
	};
}